package s9_树.tree3_线索化二叉树;


/**
 * @author wisdomelon
 * @date 2020/8/15 0015
 * @project data_study
 * @jdk 1.8
 *
 * 线索化二叉树：
 * 1.n个节点的二叉链表中含有n+1个空指针域，利用二叉链表中的空指针域，存放指向该节点在“某种遍历次序”下的前驱和后继节点的指针称为“线索”
 * 2.这种加上了线索的二叉链表称为线索链表，相应的二叉树称为线索二叉树，根据线索性质的不同，线索二叉树可分为前序线索二叉树、中序线索二叉树和后续线索二叉树三种
 * 3.一个节点的前一个节点称为前驱节点
 * 4.一个节点的后一个节点称为后继节点
 * 5.当线索化二叉树后
 *  1.left指向的是左子树，也可能是指向前驱结点
 *  2.right指向的是右子树，也可能是指向后继节点
 */
public class ThreadedBinaryTreeDemo {

    public static void main(String[] args) {
        
        HeroHode root = new HeroHode("1", "1");
        HeroHode b = new HeroHode("3", "3");
        HeroHode c = new HeroHode("6", "6");
        HeroHode d = new HeroHode("8", "8");
        HeroHode e = new HeroHode("10", "10");
        HeroHode f = new HeroHode("14", "14");

        root.setLeft(b);
        root.setRight(c);
        b.setLeft(d);
        b.setRight(e);
        c.setLeft(f);

        ThreadedBinaryTree tree = new ThreadedBinaryTree();
        tree.setRoot(root);
        tree.midThreadedNodes(root);

        HeroHode left = e.getLeft();
        System.out.println(left);
        HeroHode right = e.getRight();
        System.out.println(right);

    }
}

class ThreadedBinaryTree {
    private HeroHode root;

    private HeroHode pre;

    public void setRoot(HeroHode root) {
        this.root = root;
    }

    /**
     * 中序线索化二叉树遍历
     */
    public void midThreadedList() {
        // 存储当前遍历的节点
        HeroHode node = root;
        while(node != null) {
            // 循环找到lefttag==1的节点
            // 后面随着遍历而变化，因为当leftTag==1时，说明该节点是线索化处理后的有效节点
            while(node.getLeftTag() == 0) {
                node = node.getLeft();
            }

            // 打印当前这个节点
            System.out.println(node);

            // 如果当前节点的右指针指向的是后继节点，就一直输出
            while(node.getRightTag() == 1) {
                //获取当前节点的后继节点
                node = node.getRight();
                System.out.println(node);
            }

            // 替换这个遍历的节点
            node = node.getRight();
        }
    }

    /**
     * 二叉树中序线索化
     * @param node 当前需要被线索化的节点
     */
    public void midThreadedNodes(HeroHode node) {
        if(node == null) return;

        // 线索化左子树
        midThreadedNodes(node.getLeft());

        // 线索化当前节点
        // 处理当前节点的前驱节点
        if(node.getLeft() == null) {
            // 让当前节点的左指针指向前驱节点
            node.setLeft(pre);
            // 修改当前节点的左指针的类型
            node.setLeftTag(1);
        }

        // 处理上一个节点的后继节点
        if(pre != null && pre.getRight() == null) {
            // 前驱节点的右指针指向当前节点
            pre.setRight(node);
            // 修改前驱节点的右指针类型
            pre.setRightTag(1);
        }

        // 每处理完一个节点后，让当前节点成为下一节点的前驱节点
        pre = node;

        // 线索化右子树
        midThreadedNodes(node.getRight());
    }
}

class HeroHode {
    private String no;

    private String name;

    private HeroHode left;

    private HeroHode right;

    /** 0-指向左子树 1-指向前驱节点 */
    private int leftTag;
    /** 0-指向右子树 1-指向后继节点 */
    private int rightTag;

    public HeroHode(String no, String name) {
        this.no = no;
        this.name = name;
    }

    public String getName() {
        return name;
    }

    public HeroHode getLeft() {
        return left;
    }

    public HeroHode getRight() {
        return right;
    }

    public int getLeftTag() {
        return leftTag;
    }

    public void setLeftTag(int leftTag) {
        this.leftTag = leftTag;
    }

    public int getRightTag() {
        return rightTag;
    }

    public void setRightTag(int rightTag) {
        this.rightTag = rightTag;
    }

    public void setNo(String no) {
        this.no = no;
    }

    public String getNo() {
        return no;
    }

    public void setName(String name) {
        this.name = name;
    }

    public void setLeft(HeroHode left) {
        this.left = left;
    }

    public void setRight(HeroHode right) {
        this.right = right;
    }

    @Override
    public String toString() {
        return "HeroHode{" +
                "no=" + no +
                ", name='" + name + '\'' +
                '}';
    }

}

